1. Field of the Invention
The present invention concerns a recursive type adder for calculating the sum of two operands.
This invention is used to calculate the sum of two binary data numbers using adders in the form of integrated circuits, particularly for information processing systems wherein the adders constitute one of the fundamental operations of data processing.
The invention is classified in the category of parallel-parallel type adders. These allow addition of two operands A and B respectively comprised of binary data a.sub.1, a.sub.2, . . . , a.sub.n and b.sub.1, b.sub.2, . . . , b.sub.n. The result is furnished in parallel binary form.
2. Description of the Related Art
Generally, a parallel-parallel adder comprises a complex association of interconnected elementary series adders. Each elementary adder receives two bits to be added, belonging to each of the operands or to the intermediate results effected by other elementary adders in the complex circuit. Each adder furnishes the binary result of one addition at one output but may also furnish, at two other outputs, two bits respectively termed propagation and generation bits.
The propagation bit P.sub.k furnished by one adder AD.sub.k, of row k (full adder) in a range comprising K adders connected in series (1.ltoreq.k.ltoreq.K), conforms to the relation P.sub.k =P.sub.k .multidot.P.sub.k-1. . . P.sub.1 with P.sub.k =a.sub.k .sym.b.sub.k. In known manner, .sym. designates exclusive operator XOR.
a.sub.k and b.sub.k respectively denote the input bits from row k, to be added.
If the sum effected by each elementary adder AD.sub.k of a row is designated by local addition, it is necessary to add two bits a.sub.k and b.sub.k belonging to the two operands A and B. Three situations may arise;
(1) if a.sub.k =b.sub.k =0 no carry is generated by the elementary adder and if a carry comes from the adders in a row lower than k which effect addition of lower weight bits, this carry is then "trapped" by added AD.sub.k. Thus, bit S.sub.k of impulse 2K of the sum is a logic 1;
(2) if a.sub.k =0 and b.sub.k =1 or a.sub.k =1 and b.sub.k =0, then no carry is generated locally, but a carry coming of lower weight is propagated towards the adder in row k+1, and s.sub.k =0. If not, s.sub.k remains equal to 1; and
(3) if a.sub.k =b.sub.k =1, a carry is generated locally by adder AD and this carry is transmitted towards the adder of upper row k+1.
In the same manner, the local generation function g.sub.k for adder AD.sub.k of row k obeys the relation EQU g.sub.k =a.sub.k .multidot.b.sub.k.
This relationship of logic ".multidot." corresponds to the logical function AND.
The generative function G.sub.k of an adder AD.sub.k corresponds to an output bit of this adder, equal to 1, each time a carry appears after addition. Propagation function P.sub.k corresponds to an output bit of this adder, equal to 1, when a carry originating from an adder of the preceding row (k-1) must be propagated to the adder in the following row (k+1).
Under these conditions, the base relation of carry r.sub.k, calculated by a rapid parallel adder of row k, is written EQU r.sub.k =g.sub.k +(P.sub.k .multidot.r.sub.k-1).
In this equation the plus sign designates the logic operation OR.
The carry r.sub.k is produced by the addition of the first k bits of the two operands. This equation is valid for any value of k.
The final calculation of the sum S.sub.k is effected by a simple operator XOR EQU S.sub.k =P.sub.k .sym.r.sub.k-1.
In a series of k adders, r.sub.1 IN designates the input carry applied to the first adder in the series, and r.sub.K OUT designates the output carry of the last adder in the series.
Parallel adders functioning on this principle and using series of elementary adders of the "full adder" type are described, for example, in the following articles:
(1) the publication IEEE TRANSACTIONS ON COMPUTERS--VOLUME C31, NO. 3, March 1982, pages 260-264--in an article entitled "Regular Layout for Parallel Adders";
(2) 1983--pages 10-16--in an article entitled "Comparison of ALU Structures for VLSI Technology";
(3) the book entitled "Circuits logiques de traitement numerique d'information" ["Logic Circuits for Digital Information Processing"]--CEPAUDES edition, ECOLE NATIONAL SUPERIEURE DE L'AERONQUTIQUE ET DE L'ESPACE [National College of Aeronautics and Space]--1979--Pages 185-289.
These publications describe complex circuits for elementary adders capable of effecting the sum of two binary operands.
The essential problem posed by complex adders comprised of "full adders" arises primarily from the fact that carrys are generated by certain adders and certain carrys must be propagated. Actually, any generation or propagation of a carry requires complex connections and supplementary circuits; in the case of an integrated circuit adder, these connections and these supplementary circuits affect not only the surface of the integrated circuit, but also its performance.
Among rapid parallel adders, one of the most frequently used is the "carry select adder". In this type of adder, which comprises at least one series of elementary full adders, two parallel carry calculations are effected. The first calculation is effected with the hypothesis of an input carry being equal to 1, while the second calculation is effected with the hypothesis of an input carry equal to zero. Thus, during addition, it is not necessary to know in advance what is the carry coming from the preceding bits in order to effect addition of the subsequent bits. When the carry is effectively determined calculations effected in each of the hypotheses, the result corresponding to the valid hypothesis is selected in the time necessary for the addition.
This type of adder, while having the disadvantage of doubling a portion of the material, as two parallel calculations are performed with different hypotheses, has the advantage of increasing calculation speed. Actually, when the input carry in the first adders of the series is not known, it is possible to gain time by virtue of the two hypotheses described above, by effecting the adding calculations during the time it takes for the input carry to arrive at the input of the series of adders.
In general, parallel adders may be one of two types: "repetitive" and "recursive" type adders. In both types of adders, propagation of the carry is the essential problem.
In a repetitive type adder, an adder for n bits is constructed by adding an elementary cell (full adder) to an adder already comprising n-1 elementary cells connected in series. This structure translates the relation of recurrence of addition. To increase the propagation speed of this type of adder, it is necessary to optimize only one propagation path for the carry. The classic examples of this type of adder is the Manchester carry chain adder.
In a recursive type adder, an n bit adder is subdivided into two n/2 bit adders. In this type of adder, the carry propagation time is theoretically Log(n)T, where T designates the propagation time for an elementary cell. This recursive structure is used primarily in series adders permitting distribution of the necessary information to the different cells in optimal time. This type adder is often called a "carry look ahead adder".
Generally, manufacturing these repetitive type adders requires less silicon, but they are slower than recursive type adders, which do use a great deal of silicon.
Besides repetitive and recursive embodiments, intermediate adaptations exist which are, in effect, compromise solutions. These compromise embodiments simultaneously take advantage of the repetitive aspect of adders because of its relatively few obstructions and the recursive aspect because of its speedy performance.
One of these known compromise embodiments is an optimal carry select adder. This embodiment consists of breaking the addition up into several segments. Hypotheses are formed for each of the segments, as indicated above, regarding the carry input for each segment. The carry input for each segment is determined more and more closely with the help of a series of cells which effect the logic operation g.multidot.r+p; in this relation, g denotes a carry bit and p is a bit which indicates whether or not there is propagation of the bit. This type of adder may be termed a "g.multidot.r+p adder".
The adder wherein the carry input is equal to zero has for the carry output, the carry generated by the segment, designated by G.sub.t.
The adder wherein the carry input is equal to 1 has its own calculated carry as the carry output. The propagation bit is equal to 1 and is designated by P.sub.t when there is propagation in the segment. If r.sub.in designates the real carry entering a segment, the carry output r.sub.out is obtained by the logic operation r.sub.OUT =G.sub.t +P.sub.t .multidot.r.sub.IN.
Calculations are performed in parallel in the different segments and optimizing an adder of this type depends upon the number of bits which each segment must calculate to render all the propagation paths critical in a series structure adder of predetermined hierarchy. The definitions of critical pathways, the series structure and the hierarchical levels are described in the publications previously cited.
In an optimal carry select adder, the number of elementary addition cells may be progressively increased in each new segment, so that the calculation time necessary for one segment is equal to that of the preceding segment, increased by the selection time of the carry. In this case the result is an optimal carry select adder.
Another known compromise embodiment is the use of a carry skip adder. This type of adder resembles the previous one in propagation of the carry. It differs from the preceding adder in that for each segment, only one repetitive type adder is used (comprising several elementary addition cells connected in series) wherein the input carry is the carry coming from the selection cell of the preceding carry. However, it is necessary to calculate the propagation function at each segment to control the corresponding selection cell. The name of this adder comes from the fact that the carry may be more quickly propagated, by a line parallel to the series adders and which is a far more rapid path than that which crosses the series of adders.
This adder has one disadvantage in relation to the preceding one: to render all its paths critical for the sum to be calculated as well as for the carry, when proceeding from low to high weight bits to be added, to increase the size of the segments (i.e., the number of elementary adders in series in each segment), then to decrease their size in the middle of the adder. Decreasing the size of the segments is actually compulsory so as to prevent the carry from being obtained too rapidly in relation to sum S.
In the optimal carry select adder, the size of the segments increases in linear progression. The time for selecting the sum varies with the hypothesis of a selection time equal to a propagation time across a full adder. In known manner, approximately n(n+1)/2 bits are calculated in time nT, n.sup.2 /2 bits are calculated in nT and n bits are calculated in .sqroot.2nT (T designating the time necessary to calculate the addition of two data bits).
In the optimal carry skip adder, the size of the segments increases in linear progression for the first half of bits to be added and then decreases in the same manner. It is said that for this type of adder, approximately n bits are calculated in a time equal to 2.sqroot.nt.
Generally, these two embodiments behave asymptotically at radix 2 n, and if the optimal carry skip adder is slower than the optimal carry select adder, it is, on the other hand, more economical in terms of substrate required for manufacture.
Adders using a branching system (carry look ahead adders, for example), totally repetitive, occupy considerable space which increases by n log(n) (n being the number of respective data bits to be added), while totally repetitive embodiments are very slow.
Optimal embodiments, such as the carry skip adder or the carry select adder, are an interesting compromise but are not totally satisfactory: while they require about the same surface as a carry skip adder, they cannot attain the same speed as a carry select adder.
The goal of the invention is to overcome these disadvantages and particularly to achieve an adder which uses about the same space as a carry skip adder, while at the same time performing nearly as fast as a carry look ahead adder.
As will later be seen in detail, the adder which is the subject of the invention has a novel structure termed recursive which results in a considerably elevated speed/surface ratio.